/**
 * @Author: wanqian
 * @Date: 2021/3/1 10:17
 */
public class PrimDemo {

    public static void main(String[] args) {
        char[] vers = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = new int[][]{
                {0, 5, 7, 0, 0, 0, 2},
                {5, 0, 0, 9, 0, 0, 3},
                {7, 0, 0, 0, 8, 0, 0},
                {0, 9, 0, 0, 0, 4, 0},
                {0, 0, 8, 0, 0, 5, 4},
                {0, 0, 0, 4, 5, 0, 6},
                {2, 3, 0, 0, 4, 6, 0}
        };
        Graph graph = new Graph(vers, weight);
        prim(graph);
    }

    /**
     * 普力姆算法求连通所有节点的最短路径
     *
     * @param graph
     */
    public static void prim(Graph graph) {
        int[][] weight = graph.weight;
        int[] visited = new int[graph.verNum];
        visited[0] = 1;
        //大循环graph.verNum - 1次，建立graph.verNum - 1条路径
        for (int i = 0; i < graph.verNum - 1; i++) {
            int minVal = 0;
            int fromIndex = 0;
            int toIndex = 0;
            //从已访问的顶点出发，寻找到达未访问顶点最近路径
            for (int j = 0; j < weight.length; j++) {
                //遍历已访问节点
                if (visited[j] == 1) {
                    //遍历未访问且路径最短的顶点(0为不能访问)
                    for (int k = 0; k < weight.length; k++) {
                        if (visited[k] != 1 && weight[j][k] > 0 && (minVal == 0 || weight[j][k] < minVal)) {
                            minVal = weight[j][k];
                            fromIndex = j;
                            toIndex = k;
                        }
                    }
                }
            }
            //标记最近未访问节点为已访问
            visited[toIndex] = 1;
            System.out.println(String.format("顶点%s 至 顶点%s, 权值为%d", graph.vers[fromIndex], graph.vers[toIndex], graph.weight[fromIndex][toIndex]));
        }
    }

    public static class Graph {
        //顶点数
        private int verNum;
        //顶点名
        private char[] vers;
        //路径权值
        private int[][] weight;

        public Graph(char[] vers, int[][] weight) {
            this.verNum = vers.length;
            this.vers = vers;
            this.weight = weight;
        }
    }

}
